package jiggle;

import java.util.ArrayList;


// Class for graphs. */


public class Graph extends Cell {
	
	// for debugging purposes
	public static int cnt = 0;
	public int id = cnt++;
  
	public ArrayList<Cell> vertices = new ArrayList<Cell> (1);
	public ArrayList<Edge> edges = new ArrayList<Edge>();
	public int getNumberOfVertices() {
		return vertices.size();
	}
	

	/* NOTE: the above are made publicly accessible for reasons of
	efficiency.  They should NOT, however, be modified except by
	insertVertex, deleteVertex, insertEdge, and deleteEdge methods
	below. */
    
	/*
	 * sets up a 2-dimensional graph
	 */
	public Graph () {}

	public Graph (int d) {setDimensions (d);}

	public Vertex insertVertex() {
        Vertex v = new Vertex(this);
        insertVertex(v);
        return v;
    }

	public Cell insertVertex(Cell v) {
        vertices.add(v);
        v.setContext(this);
        return v;
    }

	public Edge insertEdge (Vertex from, Vertex to) {
		return insertEdge (from, to, false);
	}

	/*
    private static int cnt = 0;
    private int id = cnt++;
    private String getId() {
        return "/" + id + "/";
    }
    */
	
    public static String getEdgeAtStr(Edge e) {
        String retVal = "";
        retVal += e.getFrom();
        retVal += " --> ";
        retVal += e.getTo();
        return retVal;
    }

	public Edge insertEdge (Vertex from, Vertex to, boolean dir) {
		return insertEdge(new Edge (this, from, to, dir));
	}

	public Edge insertEdge (Edge e) {
        //System.err.println("Inserting EDGE: " + getId() + " " + getEdgeAtStr(e));
		e.getFrom().insertNeighbor (e); 
		e.getTo().insertNeighbor (e);
        edges.add(e);
        //System.err.println("EDGE Cnt: " + edges.size());
        //for (Edge edge : edges) {
		//	System.err.println("EDGE Cnt - Edge:" + getEdgeAtStr(edge));
		//} 
        //System.err.println("EDGE Cnt: " + edges.size());
		return e;
	}
	
	public void deleteVertex (Vertex v) {
		for (int i = 0; i < v.undirectedEdges.size(); i++) {
			Edge e = (Edge) v.undirectedEdges.get(i);
			((Vertex)v.undirectedNeighbors.get(i)).deleteNeighbor (e);
            edges.remove(e);
		}
		for (int i = 0; i < v.inEdges.size(); i++) {
			Edge e = (Edge) v.inEdges.get(i);
			((Vertex)v.inNeighbors.get(i)).deleteNeighbor (e);
            edges.remove(e);
		}
		for (int i = 0; i < v.outEdges.size(); i++) {
			Edge e = (Edge) v.outEdges.get(i);
			((Vertex)v.outNeighbors.get(i)).deleteNeighbor (e);
            edges.remove(e);
		}
		if (!vertices.remove(v))
			throw new Error (v + " not found");
	}

	public void deleteEdge (Edge e) {
		e.getFrom ().deleteNeighbor (e); e.getTo ().deleteNeighbor (e);
	}
	
	public boolean centralDistances = true;
	public double pairwiseWeights(AbstractForceLaw forceLaw, Cell c1, Cell c2) {
	    if (centralDistances)
	        return pairwiseWeightsCentral(forceLaw, c1, c2); 
	    else
	        return pairwiseWeightsExternal(forceLaw, c1, c2); 
	}
	public double pairwiseWeights(AbstractForceLaw forceLaw, Cell cell, double [] coords) {
	    if (centralDistances)
	        return pairwiseWeightsCentral(forceLaw, cell, coords); 
	    else
	        return pairwiseWeightsExternal(forceLaw, cell, coords); 
	}
	
	// computes distances from the centers of the cells
	public double pairwiseWeightsCentral(AbstractForceLaw forceLaw, Cell c1, Cell c2) {
		double pref = forceLaw.preferredEdgeLength + Cell.sumOfRadii (c1, c2);
		double curr = Cell.getDistance (c1, c2);
		return forceLaw.pairwiseWeights(pref, curr);
	}

	public double pairwiseWeightsCentral(AbstractForceLaw forceLaw, Cell cell, double [] coords) {
		double pref = forceLaw.preferredEdgeLength + Cell.radius (cell, coords);
		double curr = Cell.getDistance (cell, coords);
		return forceLaw.pairwiseWeights(pref, curr);
	}
	
	// computes external distances
	public double pairwiseWeightsExternal(AbstractForceLaw forceLaw, Cell c1, Cell c2) {
		double pref = forceLaw.preferredEdgeLength;
		double curr = Cell.getDistance (c1, c2) - Cell.sumOfRadii (c1, c2);
		return forceLaw.pairwiseWeights(pref, curr);
	}

	public double pairwiseWeightsExternal(AbstractForceLaw forceLaw, Cell cell, double [] coords) {
		double pref = forceLaw.preferredEdgeLength;
		double curr = Cell.getDistance (cell, coords) - Cell.radius (cell, coords);
		return forceLaw.pairwiseWeights(pref, curr);
	}

	@Override
    public void recomputeBoundaries () {
		int d = getDimensions ();
		double lo [] = getMin (), hi [] = getMax ();
		for (int i = 0; i < d; i++) {
			lo [i] = Double.MAX_VALUE; hi [i] = -Double.MAX_VALUE;
		}
		for (int i = 0; i < vertices.size(); i++) {
			Cell v = vertices.get(i); 
			double c [] = v.getCoords ();
			for (int j = 0; j < d; j++) {
				lo [j] = Math.min (lo [j], c [j]);
				hi [j] = Math.max (hi [j], c [j]);
			}
		}
		recomputeSize ();
	}

	// The isConnected method tests whether a graph is connected.
	// An empty graph is considered to be not connected.

	boolean isConnected () {
		if (vertices.size() == 0) return false;
		for (int i = 0; i < vertices.size(); i++)
			vertices.get(i).booleanField = false;
		numberOfMarkedVertices = 0;
		dft (vertices.get(0));
		return (numberOfMarkedVertices == vertices.size());
	}
	private int numberOfMarkedVertices = 0;
	private void dft (Cell c) {
	    if (c instanceof Vertex) dft((Vertex)c);
	}
	private void dft (Vertex v) {
		v.booleanField = true; ++numberOfMarkedVertices;
		for (int i = 0; i < v.undirectedNeighbors.size(); i++) {
			Vertex neighbor = (Vertex) v.undirectedNeighbors.get(i);
			if (! neighbor.booleanField) dft (neighbor);
		}
		for (int i = 0; i < v.inNeighbors.size(); i++) {
			Vertex neighbor = (Vertex) v.inNeighbors.get(i);
			if (! neighbor.booleanField) dft (neighbor);
		}
		for (int i = 0; i < v.outNeighbors.size(); i++) {
			Vertex neighbor = (Vertex) v.outNeighbors.get(i);
			if (! neighbor.booleanField) dft (neighbor);
		}
	}
}
